class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    //优先级
   /*
   操作数直接入数字栈
   操作符入栈有规则：
   如果符号栈为空，直接入栈
   如果不空，看优先级，如果栈外的优先级比栈顶的优先级直接入栈
   否则，就出栈，从数字栈中拿出两个数计算，将计算的结果Δ入数字栈
   左括号直接入栈
   右括号的优先级最低，要等符号栈里面的符号都出栈计算完毕，遇到左括号一起出栈
   */
    stack<int> num;
    stack<char> op;
    
    void cal()
    {
        int b=num.top();num.pop();
        int a=num.top();num.pop();
        char c=op.top();op.pop();
        int r;
        if(c=='+')
            r=a+b;
        else if(c=='-')
            r=a-b;
        else if(c=='*')
            r=a*b;
        num.push(r);
    }
    int solve(string s) {
        // write code here
         unordered_map<char, int>hash{{'+',1},{'-',1},{'*',2}};
        for(int i=0;i<s.size();i++)
        {
            char c=s[i];
            if(isdigit(c)) //是数字
            {
                int x=0,j=i;
                while(j<s.size()&&isdigit(s[j]))
                   x=x*10+s[j++]-'0';
                i=j-1;
                num.push(x);
            }else if(c=='(')
            {
                op.push(s[i]);
            }else if(c==')') //右括号优先级最小
            {
                while(op.top()!='(')
                    cal(); //从数字栈中拿出两个数，从符号栈拿出一个操作符，计算，将计算的结果放在数字栈中
                 op.pop(); //遇到‘(’出栈
            }else
            {
                //符号栈不空，栈外的优先级小于等于栈内，先计算
                while(op.size()&&hash[c]<=hash[op.top()])
                     cal();
                //栈空或者栈外优先级高直接入栈
                 op.push(c); 
            }
        }
        while(op.size())
            cal();
        return num.top();
    }
};